//
//  XBStaticLink.c
//  数据结构算法和笔试题
//
//  Created by Ceasar on 16/6/2.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBStaticLink.h"

//------------索引从1 开始


//获取一个备用节点的下标
int XBGetNewIdx (XBStaticLinkList list)
{
    int i = list[0].nextIdx;//获取新元素的下标
    if (list[0].nextIdx<MAX_SIZE-1) {
        list[0].nextIdx = list[i].nextIdx;//更新备用节点的位置，所以必须保证list[i].next是没有用过的
    }
    return i;
}

void initXBStaticList(XBStaticLinkList sList)
{
    int i=0;
    for ( i =0; i<MAX_SIZE-1; i++) {//sList[0]不存数据。sList[0].data 表示的是新元素插入的索引位置
        
        sList[i].nextIdx=i+1;
    }
    sList[MAX_SIZE-1].nextIdx=0;//最后一个设置为0表示第一个插入的元素位置是0，也可以设置为其他的，startIdx.
    sList[MAX_SIZE-1].data=0;//保存当前的数目
    /**
     sList[MAX_SIZE-1].cur=startIdx;
     则sList[startIdx].data 用来存储下一个要插入数据的节点，但是把首尾单独操作比较方便。所以这样设置
     此时sList[i].nextIdx = 0 和 尾部指针相同，所以可以表示数据为空
     */
}

int isXBLinkStaticEmpty(XBStaticLinkList sList)
{
    return sList[MAX_SIZE-1].data==0;//表示数组里面的没有数据
}

int addItemToXBStaticLinkList(XBStaticLinkList  sList,DATATYPE obj)
{
   int newIdx = XBGetNewIdx(sList);//获取一个新的节点
   if (newIdx<MAX_SIZE-1) {//表示没有满，
        sList[newIdx].data=obj;//进行插入
        //更新末尾指针的位置
        sList[0].nextIdx=sList[newIdx].nextIdx;
        sList[MAX_SIZE-1].nextIdx= 1;//
        sList[MAX_SIZE-1].data++; //更新数目
        return SUCCESS;
    }
    return FAIL;
}

void clearXBStaticLinkList(XBStaticLinkList  sList)
{
    while (!isXBLinkStaticEmpty(sList)) {
        
        deleteItemInXBStaticLinkList(sList, sList[MAX_SIZE-1].data);
    }
}

int getItemFromXBStaticLinkListByIndex(XBStaticLinkList sList,int idx,DATATYPE * obj)
{
    if (!isXBLinkStaticEmpty(sList)) {
        
        int startIdx = sList[MAX_SIZE-1].nextIdx;;
        int i =1;
        while (i<=sList[MAX_SIZE-1].data) {
            
            if (i==idx ) {
                *obj = sList[startIdx].data;
                break;
            }
            startIdx = sList[startIdx].nextIdx;
            i++;
        }
        
    }
    return FAIL;
}

int findItemInXBStaticLinkList(XBStaticLinkList sList,DATATYPE obj)
{
    if (!isXBLinkStaticEmpty(sList)) {
        
        int startIdx = sList[MAX_SIZE-1].nextIdx;
        int endIdx = sList[0].nextIdx;
        int i =1;
        while (startIdx!=endIdx) {
            
            if (sList[startIdx].data==obj) {
                return i;
            }
            startIdx = sList[startIdx].nextIdx;
            i++;
        }
        return FAIL;
    }
    return FAIL;
}

int insertItemInXBStaticLinkList(XBStaticLinkList sList,int idx,DATATYPE obj)
{
    
    if (idx<1||idx>getLengthForXBStaticLinkList(sList)) {
        return FAIL;
    }
    if (sList[MAX_SIZE-1].nextIdx == 0) {//
        
        return FAIL;
    }
    int i = XBGetNewIdx(sList);//现在最后边找一个节点
    if (i<MAX_SIZE-1) {
       sList[i].data = obj;
        //寻找节点的位置
        int k= 1;
        int tempNext = MAX_SIZE-1;
        while (tempNext!=sList[0].nextIdx&&k<idx) {
            
            tempNext = sList[tempNext].nextIdx;
            k++;
        }
        sList[i].nextIdx = sList[tempNext].nextIdx;//把当前节点的下一个节点的位置赋值给新节点
        sList[tempNext].nextIdx = i;//更新新的位置的索引
        sList[MAX_SIZE-1].data++;//
        return SUCCESS;
    }
    return FAIL;
}

//释放一个节点
void Free_SSL (XBStaticLinkList slist,int k)
{
    slist[k].nextIdx = slist[0].nextIdx;//保留最新元素的位置
    slist[0].nextIdx = k;//把将要删除的位置留给slist[0]，表示这个位置是以后有元素来了要占据这个位置
}
int deleteItemInXBStaticLinkList(XBStaticLinkList sList,int idx)
{
    int j,k=1;
    if (idx < 1 || idx> getLengthForXBStaticLinkList(sList)) {
        return FAIL;
    }
    int tempNext = MAX_SIZE-1;
    while (tempNext!=sList[0].nextIdx&&k<idx) {
        
        tempNext = sList[tempNext].nextIdx;
        k++;
    }
    j = sList[tempNext].nextIdx;//删除保留下一个元素
    sList[tempNext].nextIdx = sList[j].nextIdx;
    
    sList[MAX_SIZE-1].data--;//数目总数要减一
    Free_SSL(sList,j);
    return SUCCESS;
}

// 返回里面数据元素的个数
int getLengthForXBStaticLinkList(XBStaticLinkList sList)
{
    return sList[MAX_SIZE-1].data;
}

void printXBStaticLinkList(XBStaticLinkList sList)
{
    int startIdx = sList[MAX_SIZE-1].nextIdx;
    printf("数据：\n");
    int i = 1;
    while (i<=sList[MAX_SIZE-1].data) {
        printf("%d ",sList[startIdx].data);
        startIdx = sList[startIdx].nextIdx;
        i++;
    }
    putchar('\n');
}

int replaceXBStaticLinkList(XBStaticLinkList sList,int idx,DATATYPE obj)
{
    int startIdx = sList[MAX_SIZE-1].nextIdx;
    if (idx>sList[MAX_SIZE-1].data&&idx<1) {
        return FAIL;
    }
    int i =1;
    while (i<=sList[MAX_SIZE-1].data) {
        if (idx==i) {
            sList[startIdx].data = obj;
            return SUCCESS;
        }
        startIdx = sList[startIdx].nextIdx;
        i++;
    }
    return FAIL;
}

